package leetcode;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class LeetCodeSolution {

    public static void main(String[] args) {
        System.out.println(new Date().getTime());
        int[][] nums = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] newInterval = {4, 8};
        System.out.println("re:" + insert(nums, newInterval));

        System.out.println(new Date().getTime());
    }

    // https://leetcode.cn/problems/insert-interval/description/?envType=study-plan-v2&envId=top-interview-150
    // 插入区间
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> a = new ArrayList<>();
        int i = 0;
        int len = intervals.length;
        // 遍历获取左边不重合的区间
        while (i < len && intervals[i][1] < newInterval[0]) {
            a.add(intervals[i]);
            i++;
        }
        // 遍历获取重合区间
        while (i < len && intervals[i][1] >= newInterval[0] && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        a.add(newInterval);

        while (i < len && intervals[i][0] > newInterval[1]) {
            a.add(intervals[i]);
            i++;
        }

        return a.toArray(new int[0][]);
    }

    // https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-interview-150
    // 合并区间
    public static int[][] merge(int[][] intervals) {
        Map<Integer, Integer> imap = new HashMap<>();
        for (int[] interval : intervals) {
            boolean flag = true;
            int s = interval[0], e = interval[1];
            // 注:需要用 iterator 删除map
            Iterator<Map.Entry<Integer, Integer>> iterator = imap.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Integer> entry = iterator.next();
                if ((entry.getKey() > interval[1] || entry.getValue() < interval[0])) {
                } else {
                    flag = false;
                    iterator.remove();
                    s = Math.min(entry.getKey(), s);
                    e = Math.max(entry.getValue(), e);
                }
            }
            if (flag) {
                imap.put(interval[0], interval[1]);
            } else {
                imap.put(s, e);
            }
        }
        int[][] result = new int[imap.size()][2];
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : imap.entrySet()) {
            System.out.println(entry.getKey() + "---" + entry.getValue());
            result[i][0] = entry.getKey();
            result[i][1] = entry.getValue();
            i++;
        }
        return result;
    }

    // https://leetcode.cn/problems/summary-ranges/description/?envType=study-plan-v2&envId=top-interview-150
    // 汇总区间
    public static List<String> summaryRanges(int[] nums) {
        List<String> results = new ArrayList<>();
        if (nums.length == 0) {
            return results;
        }
        if (nums.length == 1) {
            results.add(nums[0] + "");
            return results;
        }
        int left = nums[0];
        int left_temp = nums[0];
        String temp = left + "";
        for (int i = 1; i < nums.length; i++) {
            if (left_temp + 1 != nums[i]) {
                if (left_temp == left) {
                    results.add(temp);
                } else {
                    results.add(temp + "->" + left_temp);
                }
                left = nums[i];
                temp = nums[i] + "";
            }
            if (i == nums.length - 1) {
                if (left != nums[i]) {
                    results.add(temp + "->" + nums[i]);
                } else {
                    results.add(temp);
                }
            }
            left_temp = nums[i];
        }
        return results;
    }

    // https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-interview-150
    // 最长连续序列
    public static int longestConsecutive(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int t = nums[0];
        int result = 1;
        int temp = 1;
        for (int i = 1; i < nums.length; i++) {
            if (t == nums[i]) {

            } else if ((t + 1) == nums[i]) {
                temp++;
            } else {
                temp = 1;
            }
            t = nums[i];
            result = Math.max(result, temp);
        }
        return result;
    }

    // https://leetcode.cn/problems/contains-duplicate-iii/description/
    // 存在重复元素 III   也超时。。。。
    public static boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        // value、index 存储用于校验的键值
        Map<Integer, Integer> flag = new HashMap<>();

        boolean result = false;
        for (int i = 0; i < nums.length; i++) {
            //兼容 abs(nums[i] - nums[j]) <= valueDiff
            for (int val = 0; val <= valueDiff; val++) {
                if (flag.containsKey(nums[i] - val)) {
                    int flag_index = flag.get(nums[i] - val);
                    //i != j,
                    if (i != flag_index) {
                        //兼容 abs(i - j) <= indexDiff
                        for (int ind = 0; ind <= indexDiff; ind++) {
                            if (Math.abs(i - flag_index) <= ind) {
                                result = true;
                            } else {
                                flag.put(nums[i], i);
                            }
                        }
                    }
                }
                if (flag.containsKey(nums[i] + val)) {
                    int flag_index = flag.get(nums[i] + val);
                    //i != j,
                    if (i != flag_index) {
                        //兼容 abs(i - j) <= indexDiff
                        for (int ind = 0; ind <= indexDiff; ind++) {
                            if (Math.abs(i - flag_index) <= ind) {
                                result = true;
                            } else {
                                flag.put(nums[i], i);
                            }
                        }
                    }
                } else {
                    flag.put(nums[i], i);
                }
            }

        }
        return result;
    }

    // 存在重复元素 III 暴力超时
    public static boolean containsNearbyAlmostDuplicates(int[] nums, int indexDiff, int valueDiff) {
        int i = 0;
        int r = 1;
        while (i < nums.length - 1) {
            if (Math.abs(nums[i] - nums[r]) <= valueDiff) {
                if (r - i <= indexDiff) {
                    return true;
                } else {
                    i++;
                    r = i;
                }
            }
            r++;
            if (r == nums.length) {
                i++;
                r = i + 1;
            }
        }
        return false;
    }

    // https://leetcode.cn/problems/contains-duplicate-ii/description/?envType=study-plan-v2&envId=top-interview-150
    // 存在重复元素 II   哈希。
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> flag = new HashMap<>();
        boolean result = false;
        for (int i = 0; i < nums.length; i++) {
            if (flag.containsKey(nums[i])) {
                if (i - flag.get(nums[i]) <= k) {
                    result = true;
                } else {
                    flag.put(nums[i], i);
                }
            } else {
                flag.put(nums[i], i);
            }
        }
        return result;
    }

    // 存在重复元素 II   双指针暴力超时。
    public static boolean containsNearbyDuplicate2(int[] nums, int k) {
        int i = 0;
        int r = 1;
        while (i < nums.length - 1) {
            if (nums[i] == nums[r]) {
                if (r - i <= k) {
                    return true;
                } else {
                    i++;
                    r = i;
                }
            }
            r++;
            if (r == nums.length) {
                i++;
                r = i + 1;
            }
        }
        return false;
    }

    // https://leetcode.cn/problems/happy-number/?envType=study-plan-v2&envId=top-interview-150
    // 快乐数 快慢指针方法
    public static boolean isHappy(int n) {
        int slow = n;
        int fast = n;
        do {
            slow = squareSum(slow);
            fast = squareSum(fast);
            fast = squareSum(fast);
        } while (slow != fast);
        if (fast != 1)
            return false;
        return true;
    }

    static int squareSum(int m) {
        int result = 0;
        while (m != 0) {
            result += (m % 10) * (m % 10);
            m /= 10;
        }
        return result;
    }

    // https://leetcode.cn/problems/two-sum/description/?envType=study-plan-v2&envId=top-interview-150
    // 两数之和
    public static int[] twoSums(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    // https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-interview-150
    // 字母异位词分组
    public static List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<Integer>> mapFlag = new HashMap<>();
        List<List<String>> result = new ArrayList<>();
        // 思路：遍历、排序、比对、入数
        for (int i = 0; i < strs.length; i++) {
            String temp = Arrays.stream(strs[i].split("")).sorted().collect(Collectors.joining());
            if (mapFlag.containsKey(temp)) {
                List<Integer> integers = mapFlag.get(temp);
                integers.add(i);
                mapFlag.put(temp, integers);
            } else {
                List<Integer> tempL = new ArrayList<>();
                tempL.add(i);
                mapFlag.put(temp, tempL);
            }
        }
        for (Map.Entry<String, List<Integer>> entry : mapFlag.entrySet()) {
            // System.out.println(entry.getKey()+entry.getValue());
            List<String> strings = new ArrayList<>();
            for (Integer integer : entry.getValue()) {
                strings.add(strs[integer]);
            }
            result.add(strings);
        }
        return result;
    }

    // https://leetcode.cn/problems/valid-anagram/description/?envType=study-plan-v2&envId=top-interview-150
    // . 有效的字母异位词
    public static boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> ss = new HashMap<>();
        Map<Character, Integer> ts = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            ss.put(s.charAt(i), ss.getOrDefault(s.charAt(i), 0) + 1);
            ts.put(t.charAt(i), ts.getOrDefault(t.charAt(i), 0) + 1);
        }
        for (Map.Entry<Character, Integer> entry : ss.entrySet()) {
            System.out.println(ts.get(entry.getKey()) + "----" + entry.getValue() + "----" + entry.getKey());
            if (!Objects.equals(ts.get(entry.getKey()), entry.getValue()))
                return false;
        }
        return true;
    }


    // https://leetcode.cn/problems/word-pattern/description/?envType=study-plan-v2&envId=top-interview-150
    // 单词规律
    public static boolean wordPattern(String pattern, String s) {
        List<String> ls = Arrays.asList(s.split(" "));
        int n = pattern.length();
        if (n != ls.size()) return false;
        for (int i = 0; i < n; i++) {
            if (pattern.indexOf(pattern.charAt(i)) != ls.indexOf(ls.get(i)))
                return false;
        }
        return true;
    }

    // https://leetcode.cn/problems/isomorphic-strings/description/?envType=study-plan-v2&envId=top-interview-150
    // 同构字符串
    // 给定两个字符串 s 和 t ，判断它们是否是同构的。
    // 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
    // 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
    public static boolean isIsomorphic(String s, String t) {
        // 建立映射关系 ，若出现与映射关系中不一致的 即不符合要求
        Map<Character, Character> s2t = new HashMap<>();
        Map<Character, Character> t2s = new HashMap<>();
        int len = s.length();
        for (int i = 0; i < len; ++i) {
            char x = s.charAt(i), y = t.charAt(i);
            if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
                return false;
            }
            s2t.put(x, y);
            t2s.put(y, x);
        }
        return true;
    }

    // https://leetcode.cn/problems/ransom-note/?envType=study-plan-v2&envId=top-interview-150
    // 赎金信
    public static boolean canConstruct(String ransomNote, String magazine) {
        Map<String, Integer> mz = new HashMap<>();
        for (String s : magazine.split("")) {
            Integer a = mz.getOrDefault(s, 0);
            mz.put(s, ++a);
        }
        for (String s : ransomNote.split("")) {
            Integer a = mz.getOrDefault(s, 0);
            if (--a < 0) {
                if (ransomNote.contains(s)) {
                    return false;
                }
            }
            mz.put(s, a);
        }
        return true;
    }

    // https://leetcode.cn/problems/spiral-matrix/?envType=study-plan-v2&envId=top-interview-150
    // 螺旋矩阵  消除法 无需记录已遍历节点
    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        // 定义矩阵上下左右边界
        int left = 0, right = matrix[0].length - 1, upper = 0, down = matrix.length - 1;

        while (true) {
            // 遍历第一行
            for (int i = left; i <= right; i++) {
                result.add(matrix[left][i]);
            }
            // 更新上边界，如果没有下一行了 遍历完毕，结束循环
            if (++upper > down) break;
            // 遍历右侧第一列
            for (int i = upper; i <= down; i++) {
                result.add(matrix[i][right]);
            }
            // 更新右边界
            if (--right < left) break;
            for (int i = right; i >= left; i--) {
                result.add(matrix[down][i]);
            }
            // 更新下边界
            if (--down < upper) break;
            for (int i = down; i >= upper; i--) {
                result.add(matrix[i][left]);
            }
            // 更新左边界
            if (++left > right) break;
        }

        return result;
    }

    //螺旋矩阵 官方题解
    public static List<Integer> spiralOrder0(int[][] matrix) {
        List<Integer> order = new ArrayList<>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        // 创建同比例二维矩阵容器 用于存储已遍历节点
        boolean[][] visited = new boolean[rows][columns];
        int total = rows * columns;
        int row = 0, column = 0;
        // 根据螺旋矩阵前进防线，定义运算规则数组
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        // 默认方向 首行向右
        int directionIndex = 0;
        for (int i = 0; i < total; i++) {
            order.add(matrix[row][column]);
            visited[row][column] = true;
            // 使用矩阵规则计算当前防线下一节点位置下标
            int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
            // 根据下一节点坐标判断 每当走到尽头： 行头、列头、或走到已遍历的节点时 变更前进方向
            if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            // 更新实际下一坐标数据
            row += directions[directionIndex][0];
            column += directions[directionIndex][1];
        }
        return order;
    }


    // https://leetcode.cn/problems/valid-sudoku/?envType=study-plan-v2&envId=top-interview-150
    // 有效的数独
    public static boolean isValidSudoku(char[][] board) {
        // 构造 行 、列表、块 三种类型的查重存储器  【9】【10】  9表示第几行几列几块  10 用于放置某个独立行、列、块中的 数据存在标识
        int[][] h = new int[9][10];
        int[][] l = new int[9][10];
        int[][] box = new int[9][10];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                if (board[i][j] != '.') {
                    // 判断是否已存在 ，若未存在 更新入存储器 若已存在直接返回false
                    // 直接使用当前值 作为存储器下标进行判断，【所有下标默认为0，若已存在存入1
                    int temp = board[i][j] - '0';
                    // i 行、 j、列  (i+1)/3+j box
                    if (h[i][temp] == 1)
                        return false;
                    if (l[j][temp] == 1)
                        return false;
                    int[] box_temp = box[(i / 3) * 3 + j / 3];
                    if (box_temp[temp] == 1)
                        return false;

                    // 已判定未存在，存入已存在表示
                    h[i][temp] = 1;
                    l[j][temp] = 1;
                    box_temp[temp] = 1;

                }
            }
        }

        return true;
    }

    // https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-interview-150
    // 最小覆盖子串  滑动窗口
    public static String minWindow(String s, String t) {
        //1.维护两个map记录窗口中的符合条件的字符以及need的字符
        Map<Character, Integer> window = new HashMap<>();
        Map<Character, Integer> need = new HashMap<>();//need中存储的是需要的字符以及需要的对应的数量
        for (char c : t.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);
        int left = 0, right = 0;//双指针
        int count = 0;//count记录当前窗口中符合need要求的字符的数量,当count == need.size()时即可shrik窗口
        int start = 0;//start表示符合最优解的substring的起始位序
        int len = Integer.MAX_VALUE;//len用来记录最终窗口的长度，并且以len作比较，淘汰选出最小的substring的len

        //一次遍历找“可行解”
        while (right < s.length()) {
            //更新窗口
            char c = s.charAt(right);
            right++;//窗口扩大
            // window.put(c,window.getOrDefault(c,0)+1);其实并不需要将s中所有的都加入windowsmap，只需要将need中的加入即可
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (need.get(c).equals(window.get(c))) {
                    count++;
                }
            }
            //System.out.println****Debug位置
            //shrink左边界，找符合条件的最优解
            while (count == need.size()) {
                if (right - left < len) {//不断“打擂”找满足条件的len最短值,并记录最短的子串的起始位序start
                    len = right - left;
                    start = left;
                }
                //更新窗口——这段代码逻辑几乎完全同上面的更新窗口
                char d = s.charAt(left);
                left++;//窗口缩小
                if (need.containsKey(d)) {
                    //window.put(d,window.get(d)-1);——bug：若一进去就将window对应的键值缩小，就永远不会满足下面的if，while也会一直执行，知道left越界，因此，尽管和上面对窗口的处理几乎一样，但是这个处理的顺序还是很关键的！要细心！
                    if (need.get(d).equals(window.get(d))) {
                        count--;
                    }
                    window.put(d, window.get(d) - 1);

                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

    // 最小覆盖子串  暴力超时
    public static String minWindow0(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        if (s.contains(t)) {
            return t;
        }
        String result = "";
        String[] s_temp = s.split("");
        Map<String, Integer> tt_map = new HashMap<>();
        for (String s1 : t.split("")) {
            int temp = tt_map.getOrDefault(s1, 0);
            tt_map.put(s1, ++temp);
        }
        // 起始遍历下标
        int flag = 0;
        for (int k = 0; k < s_temp.length - t.length() + 1; k++) {
            Map<String, Integer> t_map = new HashMap<>(tt_map);

            int l = Integer.MAX_VALUE;
            for (int i = flag; i < s_temp.length; i++) {
                if (t_map.containsKey(s_temp[i])) {
                    // 记录本次遍历符合要求起始下标
                    l = Math.min(l, i);
                    int v = t_map.get(s_temp[i]);
                    if (v == 1) {
                        t_map.remove(s_temp[i]);
                        if (t_map.isEmpty()) {
                            // 存储当前获取到的 首个包含所有字符的串  并与已获取串长度比较 起始下标
                            result = result.equals("") ? s.substring(l, i + 1) : i - l + 1 < result.length() ? s.substring(l, i + 1) : result;
                            flag = ++l;
                            break;
                        }
                    } else {
                        t_map.put(s_temp[i], --v);
                    }
                }
            }
        }
        return result;
    }

    // https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/?envType=study-plan-v2&envId=top-interview-150
    // 串联所有单词的子串
    public static List<Integer> findSubstring(String s, String[] words) {
        int w_size = words[0].length() * words.length, w_len = words[0].length();
        List<Integer> result = new ArrayList<>();
        // 排序 用于重复词 等情况  ，或者也可以使用hashmap<word,次数> 的方式 处理重复词问题
        Arrays.sort(words);
        for (int i = 0; i < s.length() + 1 - w_size; i++) {
            String temp = s.substring(i, i + w_size);
            boolean flag = true;
            String[] temps = new String[w_size / w_len];
            for (int z = 0; z < w_size / w_len; z++) {
                temps[z] = temp.substring(z * w_len, z * w_len + w_len);
            }
            Arrays.sort(temps);
            int zzz = 0;
            for (String word : words)
                if (!temps[zzz++].contains(word)) {
                    flag = false;
                    break;
                }
            if (flag) {
                result.add(i);
            }
        }
        return result;
    }

    // https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-interview-150
    // 无重复字符的最长子串
    public static int lengthOfLongestSubstring(String s) {
        if (s.length() <= 1)
            return s.length();
        int l = 0, r = 1;
        int result = 0;
        while (r < s.length()) {
            while (r < s.length() && s.substring(l, r).indexOf(s.charAt(r)) == -1) {
                r++;
            }
            result = Math.max(result, r - l);
            l++;
        }
        return result;
    }

    // https://leetcode.cn/problems/minimum-size-subarray-sum/?envType=study-plan-v2&envId=top-interview-150
    // 长度最小的子数组 滑动窗口
    public static int minSubArrayLen(int target, int[] nums) {
        if (nums.length == 0)
            return 0;
        int result = Integer.MAX_VALUE, l = 0, r = 0;
        int temp = 0;
        while (r < nums.length) {
            temp += nums[r++];
            while (temp >= target) {
                result = Math.min(result, r - l);
                temp -= nums[l++];
            }
        }

        return result == Integer.MAX_VALUE ? 0 : result;
    }

    // 长度最小的子数组 暴力超时
    public static int minSubArrayLen0(int target, int[] nums) {
        if (nums.length == 0)
            return 0;
        int result = Integer.MAX_VALUE, l = 0;
        while (l < nums.length) {
            int temp = 0, r = l;
            while (temp < target && r < nums.length) {
                temp += nums[r];
                r++;
            }
            if (temp >= target) {
                result = Math.min(r - l, result);
            }
            l++;
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }

    // https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-interview-150
    // 三数之和
    public static List<List<Integer>> threeSum(int[] nums) {
        //定义一个结果集
        List<List<Integer>> res = new ArrayList<>();
        //数组的长度
        int len = nums.length;
        //当前数组的长度为空，或者长度小于3时，直接退出
        if (len < 3) {
            return res;
        }
        //将数组进行排序
        Arrays.sort(nums);
        //遍历数组中的每一个元素
        for (int i = 0; i < len; i++) {
            //如果遍历的起始元素大于0，就直接退出
            //原因，此时数组为有序的数组，最小的数都大于0了，三数之和肯定大于0
            if (nums[i] > 0) {
                break;
            }
            //去重，当起始的值等于前一个元素，那么得到的结果将会和前一次相同
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1;
            int r = len - 1;
            //当 l 不等于 r时就继续遍历
            while (l < r) {
                //将三数进行相加
                int sum = nums[i] + nums[l] + nums[r];
                //如果等于0，将结果对应的索引位置的值加入结果集中
                if (sum == 0) {
                    // 将三数的结果集加入到结果集中
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //在将左指针和右指针移动的时候，先对左右指针的值，进行判断
                    //如果重复，直接跳过。
                    //去重，因为 i 不变，当此时 l取的数的值与前一个数相同，所以不用在计算，直接跳
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    //去重，因为 i不变，当此时 r 取的数的值与前一个相同，所以不用在计算
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    //将 左指针右移，将右指针左移。
                    l++;
                    r--;
                    //如果结果小于0，将左指针右移
                } else if (sum < 0) {
                    l++;
                    //如果结果大于0，将右指针左移
                } else {
                    r--;
                }
            }
        }
        return res;
    }

    // 三数之和  暴力超时
    public static List<List<Integer>> threeSum0(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if ((nums[i] + nums[j] + nums[k]) == 0) {
                        Integer[] temp = {nums[i], nums[j], nums[k]};
                        Arrays.sort(temp, Integer::compareTo);
                        boolean flag = true;
                        for (List<Integer> integers : result) {
                            integers.sort(Integer::compareTo);
                            if (integers.get(0) == temp[0] && integers.get(1) == temp[1] && integers.get(2) == temp[2]) {
                                flag = false;
                                break;
                            }
                        }
                        if (flag) {
                            result.add(Arrays.asList(temp));
                        }

                    }
                }
            }
        }
        return result;
    }

    // https://leetcode.cn/problems/container-with-most-water/?envType=study-plan-v2&envId=top-interview-150
    // 盛最多水的容器 双指针
    public static int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int result = Math.min(height[l], height[r]) * Math.abs(r - l);
        while (l < r) {
            // 向内收缩短板
            result = height[l] < height[r] ?
                    Math.max(result, (r - l) * height[l++]) :
                    Math.max(result, (r - l) * height[r--]);
        }
        return result;
    }

    // 盛最多水的容器 暴力解法，超时
    public static int maxArea0(int[] height) {
        int result = 0;
        for (int i = 0; i < height.length; i++) {
            for (int r = i + 1; r < height.length; r++) {
                result = Math.max(result, Math.min(height[i], height[r]) * Math.abs(r - i));
            }
        }
        return result;
    }

    // https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/?envType=study-plan-v2&envId=top-interview-150
    // 两数之和 II - 输入有序数组
    public static int[] twoSum(int[] numbers, int target) {
        int[] result = new int[2];
        int l = 0, r = numbers.length - 1;
        while ((numbers[l] + numbers[r]) != target || l == r) {
            if ((target - numbers[l]) > numbers[r]) {
                l++;
            } else {
                r--;
            }
        }
        result[0] = ++l;
        result[1] = ++r;
        System.out.println(l);
        System.out.println(r);
        return result;
    }

    // 两数之和 II - 输入有序数组 ----解法超时
    public static int[] twoSum0(int[] numbers, int target) {
        int[] result = new int[2];
        int l = 0, r = 1;
        while ((numbers[l] + numbers[r]) != target || l == r) {
            if (r >= numbers.length - 1) {
                r = ++l;

            } else {
                r++;
            }
        }
        result[0] = ++l;
        result[1] = ++r;

        return result;
    }

    // https://leetcode.cn/problems/is-subsequence/?envType=study-plan-v2&envId=top-interview-150
    // 判断子序列
    public static boolean isSubsequence(String s, String t) {

        if (s.length() > 0 && t.length() == 0) {
            return false;
        }
        if (s.length() == 0)
            return true;
        int l = 0, sl = s.length(), r = 0, tl = t.length();
        while (l < sl) {
            if (r == tl) {
                return false;
            }
            while (s.charAt(l) != t.charAt(r)) {
                r++;
                if (r == tl) {
                    return false;
                }
            }
            l++;
            r++;
        }
        System.out.println(l + "-" + r);

        return true;
    }

    // https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2&envId=top-interview-150
    // 验证回文串
    public static boolean isPalindrome(String s) {
        StringBuilder sgood = new StringBuilder();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                sgood.append(Character.toLowerCase(ch));
            }
        }

        boolean flag = true;
        int l = 0, r = sgood.toString().length() - 1;
        // r>=0 处理空串下标越界
        while (l != r && r >= 0) {
            if (sgood.charAt(l) != sgood.charAt(r)) {
                flag = false;
                break;
            }
            l++;
            r--;
        }
        return flag;
    }

    // https://leetcode.cn/problems/text-justification/description/?envType=study-plan-v2&envId=top-interview-150
    // 文本左右对齐
    public static List<String> fullJustify(String[] words, int maxWidth) {
        // 找出每行的单次
        List<String> result = new ArrayList<>();
        int sl = maxWidth + 1;
        StringBuilder temp = new StringBuilder();
        for (int i = 0; i < words.length; i++) {
            sl -= 1 + words[i].length();
            if (sl >= 0) {
                temp.append(words[i]).append(" ");
            } else {
                result.add(temp.toString());
                sl = maxWidth + 1 - words[i].length() - 1;
                temp = new StringBuilder(words[i] + " ");
            }
            if (i == words.length - 1) {
                result.add(temp.toString());
            }
        }

        // 处理每行空格分配情况
        List<String> results = new ArrayList<>();
        for (int i = 0; i < result.size(); i++) {
            StringBuilder rt = new StringBuilder(result.get(i).trim());
            if (rt.toString().split(" ").length == 1 || i == result.size() - 1) {
                // 只有一个单次 或最后一行的情况 直接填充空格
                int t = maxWidth - rt.length();
                while (t > 0) {
                    rt.append(" ");
                    t--;
                }
                results.add(rt.toString());
            } else {
                // 一行多个单词，且非最后一行的情况
                String[] temps = rt.toString().split(" ");
                // 存放空格的数量
                int nums = temps.length - 1;
                //空格数量
                int s = maxWidth - rt.toString().replaceAll(" ", "").length();
                // 分配空格 无法均分时左边多右边少，最少一个
                int[] ints = new int[nums];
                int f = 0;
                while (s > 0) {
                    ints[f] += 1;
                    s--;
                    f++;
                    if (f == nums) {
                        f = 0;
                    }
                }
                StringBuilder re = new StringBuilder();
                for (int i1 = 0; i1 < nums; i1++) {
                    int t = ints[i1];
                    re.append(temps[i1]);
                    while (t > 0) {
                        re.append(" ");
                        t--;
                    }
                }
                re.append(temps[temps.length - 1]);

                results.add(re.toString());
            }

        }
        for (String s : results) {
            System.out.println(s);
        }
        return results;
    }

    // https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/?envType=study-plan-v2&envId=top-interview-150
    // 找出字符串中第一个匹配项的下标
    public static int strStr(String haystack, String needle) {
        // return haystack.indexOf(needle);
        int hl = haystack.length(), nl = needle.length();
        for (int i = 0; i <= hl - nl; i++) {
            if (haystack.substring(i, i + nl).equals(needle)) {
                return i;
            }
        }
        return -1;
    }


    // https://leetcode.cn/problems/zigzag-conversion/description/?envType=study-plan-v2&envId=top-interview-150
    // Z 字形变换
    // 输入：s = "PAYPALISHIRING", numRows = 4
    // 输出："PINALSIGYAHRPI"
    // 解释：
    // P     I    N
    // A   L S  I G
    // Y A   H R
    // P     I
    public static String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }
        StringBuilder result = new StringBuilder();
        String[] strings = new String[numRows];
        for (int i = 0; i < numRows; i++) {
            strings[i] = "";
        }
        int sl = 0, f = 0;
        boolean flag = true;
        while (sl < s.length()) {
            strings[f] += s.substring(sl, ++sl);

            if (f == numRows - 1) {
                flag = false;
            }
            if (f == 0) {
                flag = true;
            }

            if (flag) {
                f++;
            } else {
                f--;
            }

        }
        for (String string : strings) {
            result.append(string);
        }
        return result.toString();
    }

    // https://leetcode.cn/problems/reverse-words-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150
    // 反转字符串中的单词
    public static String reverseWords(String s) {
        s = s.trim();
        String[] strings = s.split(" ");
        StringBuilder result = new StringBuilder();
        for (int i = strings.length - 1; i >= 0; i--) {
            if (!"".equals(strings[i])) {
                result.append(strings[i]);
                result.append(" ");
            }
        }
        return result.toString().trim();
    }

    // https://leetcode.cn/problems/longest-common-prefix/?envType=study-plan-v2&envId=top-interview-150
    // 最长公共前缀
    public static String longestCommonPrefix(String[] strs) {
        StringBuilder result = new StringBuilder();
        List<String[]> strings = new ArrayList<>();
        if (strs.length == 1) {
            return strs[0];
        }
        for (String str : strs) {
            strings.add(str.split(""));
        }
        boolean flag = true;
        int index = 0;
        String temp;
        while (flag) {
            if (strings.get(0).length <= index) {
                break;
            }
            temp = strings.get(0)[index];
            for (int i = 1; i < strings.size(); i++) {
                if (strings.get(i).length <= index) {
                    flag = false;
                    break;
                }
                if (!temp.equals(strings.get(i)[index])) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                result.append(temp);
            }
            index++;
        }
        return result.toString();
    }

    // https://leetcode.cn/problems/length-of-last-word/?envType=study-plan-v2&envId=top-interview-150
    // 最后一个单词的长度
    public static int lengthOfLastWord(String s) {
        String[] strings = s.split(" ");
        for (int i = strings.length - 1; i >= 0; i--) {
            if (strings[i].length() > 0)
                return strings[i].length();
        }
        return 0;
    }

    // https://leetcode.cn/problems/integer-to-roman/?envType=study-plan-v2&envId=top-interview-150
    //整数转罗马数字
    // 其他解法 优化 if else 。。。
    public static String intToRoman(int num) {
        StringBuilder result = new StringBuilder();
        while (num > 0) {
            if (num >= 1000) {
                int mc = num / 1000;
                num -= mc * 1000;
                for (int i = 0; i < mc; i++) {
                    result.append("M");
                }
            }
            if (num >= 900) {
                num -= 900;
                result.append("CM");
            }
            if (num >= 500) {
                num -= 500;
                result.append("D");
            }
            if (num >= 400) {
                num -= 400;
                result.append("CD");
            }
            // ....
        }
        return "";
    }

    // https://leetcode.cn/problems/roman-to-integer/description/?envType=study-plan-v2&envId=top-interview-150
    // 罗马数字转整数
    public static int romanToInt(String s) {
        Map<String, Integer> map = new HashMap<>();
        map.put("I", 1);
        map.put("V", 5);
        map.put("X", 10);
        map.put("L", 50);
        map.put("C", 100);
        map.put("D", 500);
        map.put("M", 1000);
        map.put("IV", 4);
        map.put("IX", 9);
        map.put("XL", 40);
        map.put("XC", 90);
        map.put("CD", 400);
        map.put("CM", 900);
        String[] chars = s.split("");
        String temp = chars[0];

        int result = 0;
        result += map.get(temp);
        for (int i = 1; i < chars.length; i++) {
            String a = temp + chars[i];
            System.out.println(a);
            if (map.containsKey(a)) {
                result += map.get(a) - map.get(temp);

            } else {
                result += map.get(chars[i]);
            }
            temp = chars[i];
        }
        return result;
    }

    // https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150
    public static int trap(int[] height) {
        //存结果
        int result = 0;
        // 存储当前下标前的最大高度
        int[] left = new int[height.length];
        left[0] = 0;
        for (int i = 1; i < height.length; i++) {
            left[i] = Math.max(height[i - 1], left[i - 1]);
        }

        int r = 0;
        for (int i = height.length - 2; i >= 0; i--) {
            r = Math.max(height[i + 1], r);
            System.out.println(left[i] + "   " + r);
            // 最大高度中较小的值为可存储的最大雨量，减去当前下标柱子高度即为当前下标可存水量
            if (Math.min(left[i], r) - height[i] > 0) {
                result += Math.min(left[i], r) - height[i];
            }
        }
        return result;
    }

    // 接雨水 by 层超时解
    public static int trap0(int[] height) {
        if (height.length < 3) {
            return 0;
        }
        //存结果
        int result = 0;
        //按层接水
        int ceng = 1;
        int maxvalue = Arrays.stream(height).max().getAsInt();
        while (ceng <= maxvalue) {
            // 记录每层非零起始下标 和起始下标间隔内减层后非0个数
            int left = Integer.MAX_VALUE, right = 0, seat = 0;
            for (int i = 0; i < height.length; i++) {
                if ((height[i] - ceng) >= 0) {
                    left = Math.min(left, i);
                    seat++;
                    right = Math.max(right, i);
                }
            }
            ceng++;
            // 计算每次结果并加到总结果中
            result += right - left + 1 - seat;
        }
        return result;
    }

    // https://leetcode.cn/problems/candy/description/?envType=study-plan-v2&envId=top-interview-150
    // 分发糖果
    public static int candy(int[] ratings) {
        if (ratings.length < 2) {
            return 1;
        }
        int[] left = new int[ratings.length];
        left[0] = 1;
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            } else {
                left[i] = 1;
            }
        }
        int[] right = new int[ratings.length];
        right[right.length - 1] = 1;
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                right[i] = right[i + 1] + 1;
            } else {
                right[i] = 1;
            }
        }
        int r = 0;
        for (int i = 0; i < ratings.length; i++) {
            r += Math.max(left[i], right[i]);
        }
        return r;
    }

    // https://leetcode.cn/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            int cur = gas[i], j = i;
            while (cur - cost[j] >= 0) {
                cur = cur - cost[j] + gas[(j + 1) % gas.length];
                j = (j + 1) % gas.length;
                if (j == i) {
                    return j;
                }
            }
        }
        return -1;
    }

    // https://leetcode.cn/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150
    public static int canCompleteCircuitBaoLI(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            int cur = gas[i], j = i;
            while (cur - cost[j] >= 0) {
                cur = cur + gas[(j + 1) % gas.length] - cost[j];
                j = (j + 1) % gas.length;
                if (j == i) {
                    return j;
                }
            }
        }
        return -1;
    }

    // https://leetcode.cn/problems/product-of-array-except-self/?envType=study-plan-v2&envId=top-interview-150
    // 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
    // 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
    // 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
    public static int[] productExceptSelf(int[] nums) {
        int[] leftRide = nums.clone();
        leftRide[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            leftRide[i] = nums[i - 1] * leftRide[i - 1];
        }

        int[] rightRide = nums.clone();
        int R = 1;

        for (int i = nums.length - 1; i >= 0; i--) {
            nums[i] = R * leftRide[i];
            R *= rightRide[i];
        }

        return nums;
    }

    // https://leetcode.cn/problems/h-index/?envType=study-plan-v2&envId=top-interview-150
    public static int hIndex(int[] citations) {
        int index = citations.length;
        int h = 0;
        while (h == 0) {
            int index_count = 0;
            for (int citation : citations) {
                if (citation >= index) {
                    index_count++;
                }
            }
            if (index <= index_count) {
                h = index;
            }
            index--;

        }
        return h;
    }

    // https://leetcode.cn/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150
    public static int jump(int[] nums) {
        // 记录当前能跳跃到的位置的边界下标
        int border = 0;
        // 记录在边界范围内，能跳跃的最远位置的下标
        int maxPosition = 0;
        // 记录所用步数
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            // 继续往下遍历，统计边界范围内，哪一格能跳得更远，每走一步就更新一次能跳跃的最远位置下标
            // 其实就是在统计下一步的最优情况
            maxPosition = Math.max(maxPosition, nums[i] + i);
            // 如果到达了边界，那么一定要跳了，下一跳的边界下标就是之前统计的最优情况maxPosition，并且步数加1
            if (i == border) {
                border = maxPosition;
                steps++;
                if (border >= (nums.length - 1)) {
                    break;
                }
            }
        }
        return steps;
    }

    // https://leetcode.cn/problems/jump-game/?envType=study-plan-v2&envId=top-interview-150
    public static boolean canJump(int[] nums) {
        boolean flag = true;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (!flag) {
                break;
            }
            if (nums[i] == 0) {
                boolean temp = false;
                if (i == 0) {
                    break;
                }
                for (int j = i - 1; j >= 0; j--) {
                    if (nums[j] > (i - j)) {
                        temp = true;
                        break;
                    }
                }
                flag = temp;
            }

        }
        return flag;
    }

    // https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/?envType=study-plan-v2&envId=top-interview-150
    public static int maxProfit(int[] prices) {
        int profit = 0;
        int left = 0, right = 0;
        int temp;
        while (right < prices.length) {
            temp = prices[right] - prices[left];
            if (temp >= 0) {
                profit = Integer.max(temp, profit);
                right++;
            } else {
                left = right++;
            }
        }
        return profit;
    }

    // https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/?envType=study-plan-v2&envId=top-interview-150
    public static int maxProfit2(int[] prices) {
        int profit = 0;
        int min_profit = Integer.MAX_VALUE;
        for (int price : prices) {
            if (min_profit > price) {
                min_profit = price;
            } else if (price - min_profit > profit) {
                profit = price - min_profit;
            }
        } 
        return profit;
    }

    // https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150
    public static int maxProfit1(int[] prices) {
        if (prices.length < 2)
            return 0;
        int profit = 0;
        int start = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] - start > 0) {
                profit = profit + prices[i] - start;
            }

            start = prices[i];
        }
        return profit;
    }

    // https://leetcode.cn/problems/rotate-array/?envType=study-plan-v2&envId=top-interview-150
    public static void rotate(int[] nums, int k) {
        int[] r = nums.clone();
        for (int i = 0; i < r.length; i++) {
            nums[(i + k) % nums.length] = r[i];
        }
    }

    // https://leetcode.cn/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150
    public static int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2 - 1];
    }

    // https://leetcode.cn/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150
    public static int majorityElement(int[] nums) {

        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        IntStream anInt = map.values().stream().mapToInt(i -> i);
        int r = 0, m = anInt.max().getAsInt();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == m) {
                r = entry.getKey();
            }
        }
        return r;
    }

}

